[알고리즘] 백준 - 내리막길

예전에도 다른 사람의 풀이를 보고 풀었더니 풀지 못했다. 이번에 확실히 정리하자. 상하좌우에 현재 자신의 위치보다 낮은 지점이 있을 경우, 해당 지점들이 갖는 경로의 수의 합을 현재 위치에 합한다. 한 번 방문해서 경로의 수를 갖고 있다면 그대로 반환하고, 방문한 점이 없던 지점이라면 새롭게 경로의 수를 구한다. 특이한 점은 현재 코드는 통과가 되지만, 코드 밑에 주석들로 대체하면 시간초과가...

DFS백준DP다시 풀 알고리즘알고리즘DFS

[알고리즘] 프로그래머스 - 경주로 건설

처음에는 DFS로, 그 다음에는 가지치기를 한 (비용이 넘어가면 진행하지 않는) DFS로 하니 70점이 나왔다. 여기서 DFS+Dp로 하려다가 실패하고, BFS로 풀었다. BFS는 다른 사람들의 풀이와 거의 비슷한데 이유는 알 수 없지만 실패했다. 나중에 시간이 날때 다시 풀어야 겠다....

BFS다시 풀 알고리즘BFS

[알고리즘] 백준 - 사다리 조작

일반적인 2차원 배열은 칸을 나타내는데 주어진 문제에서는 칸이 아닌 행과 열의 교차점이어서 그 부분이 문제를 접근하는데 많이 헷갈렸다. 문제의 searchOddNum 함수는 본인이 내려갈 지점에 가로선이 홀수개라면 절대 본인의 선 그대로 내려갈 수 없으니 미리 가지치기를 하는 것이다....

다시 풀 알고리즘백트랙킹다시 풀 알고리즘

[알고리즘] 백준 - 도로포장

처음에는 K개의 범위가 그리 크지 않아서 백트랙킹으로 완탐을 이용하여 각 경우에 대해 다익스트라를 쓰려고 했다. 하지만 메모리 초과가 났다. dp를 활용해서 풀었다....

다익스트라DP다시 풀 알고리즘DP

[알고리즘] 백준 - 소풍

처음에는 문제를 제대로 이해하지 않아 에러가 났다. 즉 데려갈 K명의 학생들은 모두 서로가 직접적으로 연결되어있어야하는데 중간 친구를 통해 연결되는 것도 된다고 생각했다. 두번째에는 충분히 가지치기를 해주지 않아 메모리 에러가 났다. 서로끼리 친구여야하므로 만약 A가 친구가 K-1명이 되지 않는다면 A는 방문할 필요가 없는 것이다. 이것을 추가해주니 통과가 됐다....

다시 풀 알고리즘백트랙킹다시 풀 알고리즘

[알고리즘] 프로그래머스 - 뉴스 클러스터링

처음에는 집합이라고 해서 바로 set를 썼는데 set를 쓰면 안된다. 왜냐하면 여기서 교집합과 합집합은 중복이 허용되기 때문이다. 파이써닉하게 엄청 잘 푼 풀이다. 만약 중복이 허용되게 집합을 합치거나 공통 부분을 추출하고 싶으면 &나 |를 사용하자....

다시 풀 알고리즘다시 풀 알고리즘